home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 03 / white.lst < prev   
File List  |  1987-02-06  |  12KB  |  483 lines
  1.   /* Listing one */
  2.   /* Subroutines for converting a pixel image
  3.      to a quadtree and output the quadtree as
  4.      locational codes
  5.  
  6.      Written by: Ronald G. White
  7.  
  8.      External routines:
  9.         px2quad - only entry point
  10.    */
  11.  
  12.   #include <stdio.h>
  13.  
  14.   /* Define structure for each node */
  15.   typedef struct qnode {
  16.     struct qnode *child[4]; /* pointers to each child */
  17.     struct qnode *next;     /* used during output */
  18.     int color;
  19.     int ntype;              /* see below for types */
  20.     int locode;             /* location code */
  21.   } QNODE, *PNODE;
  22.  
  23.   /* Node types: */
  24.   #define LEAF    1               /* no children */
  25.   #define BLEND   2               /* color of >2 kids */
  26.   #define WASH    3               /* color irrelevent */
  27.  
  28.   extern getpix(); /* return pixel color at given posn */
  29.   extern putllc(); /* output location code and color */
  30.  
  31.   static int toplevel; /* top level of tree (root node) */
  32.  
  33.   px2quad(size)
  34.   int size;
  35.   /* entry point for these routines. Control routine to
  36.      create a quadtree from the pixel image and output it
  37.      as locational codes
  38.  
  39.      input:
  40.         size - size of the image rounded up to nearest
  41.         power of two
  42.    */
  43.  
  44.   {
  45.           PNODE crtnode(), proot;
  46.  
  47.           /* Create the root node */
  48.           proot = crtnode();
  49.  
  50.           /* Calculate the toplevel number */
  51.           toplevel = 0;
  52.           while (size > 1) {
  53.                   toplevel++;
  54.                   size >>= 1;     /* divide by two */
  55.           }
  56.  
  57.           /* Build the quad tree */
  58.           proot->locode = 1;
  59.           addnode(proot, toplevel);
  60.  
  61.           /* Output it as location codes */
  62.           outtree(proot);
  63.   }
  64.  
  65.   static PNODE crtnode()
  66.   /* create a quadtree node and initialize it
  67.  
  68.      output:
  69.         returns a pointer to the node
  70.    */
  71.   {
  72.        int i;
  73.        PNODE newnode;
  74.  
  75.        /* Get space for it */
  76.        newnode = (PNODE) malloc(sizeof(QNODE));
  77.        if (newnode == NULL) {
  78.          /* Something went wrong */
  79.          fprintf(stderr,
  80.          "crtnode: malloc failure; unable to continue0);
  81.          exit(1);
  82.        }
  83.  
  84.        /* Initialize it */
  85.        for (i = 0; i < 4; i++) {
  86.                newnode->child[i] = NULL;
  87.        }
  88.        newnode->color = 0;
  89.        newnode->ntype = LEAF;
  90.        return(newnode);
  91.   }
  92.  
  93.   static addnode(pnode, level)
  94.   int level;
  95.   PNODE pnode;
  96.   /* add a new node to the quad tree
  97.      If the node is not at the bottom level, four child
  98.      nodes are created and added below the current node.
  99.      Otherwise the node color is set to that of the
  100.      corresponding pixel.
  101.  
  102.      input:
  103.         pnode    - pointer to the current node
  104.         level    - level number of the current node
  105.    */
  106.  
  107.   {
  108.        int i;
  109.        int newlevel;
  110.        PNODE crtnode(), newchild;
  111.  
  112.        /* if this node is not at the bottom level,
  113.         * add four children below this node
  114.         */
  115.        if (level > 0) {
  116.          newlevel = level - 1;
  117.          for (i = 0; i < 4; i++) {
  118.            newchild = crtnode();
  119.            pnode->child[i] = newchild;
  120.            newchild->locode = (pnode->locode << 2) + i;
  121.            addnode(newchild, newlevel);
  122.          }
  123.  
  124.          /* Remove any unnecessary children */
  125.          condense(pnode);
  126.  
  127.        /* bottom level; get actual pixel color */
  128.        } else {
  129.            pnode->color = getcolor(pnode->locode);
  130.        }
  131.   }
  132.  
  133.   static condense(pnode)
  134.   PNODE pnode;
  135.   /* examine children of the current node and
  136.      remove any that are unnecessary
  137.  
  138.      input:
  139.         pnode - pointer to current node
  140.    */
  141.  
  142.   {
  143.     int colcnt[4];
  144.     int colors[4];
  145.     int i, j;
  146.     int maxclr = 0;
  147.     int nkids;
  148.     int childclr;
  149.     PNODE pchild;
  150.  
  151.     /* Initialization */
  152.     for (i = 0; i < 4; i++) {
  153.             colcnt[i] = 0;
  154.     }
  155.  
  156.     /* Determine colors of children */
  157.     for (i = 0; i < 4; i++) {
  158.        pchild = pnode->child[i];
  159.        if (pchild->ntype == WASH) {
  160.                /* this child has no color */
  161.                continue;
  162.        }
  163.  
  164.        childclr = pchild->color;
  165.  
  166.        /* loop through colors found so far:
  167.           do we have a match?
  168.           note: we'll always "break" out of
  169.           this loop because there can be at
  170.           most four different colors.
  171.         */
  172.  
  173.        for (j = 0; j < 4; j++) {
  174.           if (colcnt[j] == 0) {
  175.              /* new color */
  176.              colors[j] = childclr;
  177.              colcnt[j] = 1;
  178.              break;
  179.  
  180.            } else if (childclr == colors[j]) {
  181.                /* existing color */
  182.                colcnt[j]++;
  183.                if (colcnt[j] > colcnt[maxclr]) {
  184.                        maxclr = j;
  185.                }
  186.                   break;
  187.            }
  188.         }
  189.     }
  190.  
  191.     /* Set node color */
  192.     pnode->color = colors[maxclr];
  193.  
  194.     /* Remove redundant children -- if more than
  195.        one child node has the same color as the
  196.        current node, then it contains redundant
  197.        information.  If the redundant node is a
  198.        leaf node, it can just be removed.  If it
  199.        is not a leaf node, mark it as a WASH type
  200.        and ignore it during output.
  201.      */
  202.  
  203.     nkids = 4;
  204.     if (colcnt[maxclr] > 1) {
  205.          /* Loop through the four children */
  206.          for (i = 0; i < 4; i++) {
  207.              pchild = pnode->child[i];
  208.  
  209.              /* If child node is already a WASH,
  210.                 nothing else can be done to it
  211.               */
  212.              if (pchild->ntype == WASH) {
  213.                      continue;
  214.              }
  215.  
  216.              childclr = pchild->color;
  217.  
  218.              /* Check for color match */
  219.              if (childclr == pnode->color) {
  220.  
  221.                   /* If child is leaf, release */
  222.                   if (pchild->ntype == LEAF) {
  223.                           relnode(pchild);
  224.                           pnode->child[i] = NULL;
  225.                           nkids--;
  226.  
  227.                   /* otherwise, mark it as a WASH */
  228.                   } else {
  229.                           pchild->ntype = WASH;
  230.                   }
  231.              }
  232.         }
  233.     }
  234.  
  235.     /* Reset node type -- a LEAF node has no children */
  236.     if (nkids == 0) {
  237.             pnode->ntype = LEAF;
  238.  
  239.     /* A BLEND node has a color that represents some
  240.        missing children, but still has some other
  241.        children that are a different color.
  242.      */
  243.     } else if (colcnt[maxclr] > 1) {
  244.             pnode->ntype = BLEND;
  245.  
  246.     /* A WASH node is necessary in the quadtree because
  247.        it points to existent children nodes, but will not
  248.        be output because its information (i.e. color) is
  249.        available either in child nodes or parent nodes.
  250.      */
  251.     } else {
  252.             pnode->ntype = WASH;
  253.     }
  254.   }
  255.  
  256.   relnode(pnode)
  257.   PNODE pnode;
  258.   /* release a node
  259.  
  260.      input:
  261.         pnode - pointer to node to release
  262.    */
  263.   {
  264.     free((char *) pnode);
  265.   }
  266.  
  267.   static getcolor(lcode)
  268.   int lcode;
  269.   /* get the color of the pixel corresponding to a
  270.      bottom level node whose position is given by a
  271.      locational code
  272.  
  273.      input:
  274.         lcode - locational code of bottom level node
  275.  
  276.      output:
  277.         returns pixel color
  278.    */
  279.   {
  280.     int dir;
  281.     int col = 0;
  282.     int level;
  283.     int row = 0;
  284.     int shift;
  285.  
  286.     /* Convert node locational code to pixel row & column
  287.        by looping through direction codes in locational
  288.        code for each level from top to bottom
  289.      */
  290.     for (level = toplevel; level > 0; level--) {
  291.  
  292.             /* shift last row & col values left one bit */
  293.             col <<= 1;
  294.             row <<= 1;
  295.  
  296.             /* calculate the position of the direction
  297.                code for this level and extract it
  298.              */
  299.             shift = (level - 1) * 2;
  300.             dir = (lcode >> shift) & 0x3;
  301.  
  302.             /* increment the col value if quadrant is in
  303.                left half, i.e. NE or SE child
  304.              */
  305.             if (dir == 1 || dir == 3) {
  306.                     col++;
  307.             }
  308.  
  309.             /* increment the row value if quadrant is in
  310.                bottom half, i.e. SW or SE child
  311.              */
  312.             if (dir == 2 || dir == 3) {
  313.                     row++;
  314.             }
  315.     }
  316.  
  317.     /* return pixel color */
  318.     return(getpix(col, row));
  319.   }
  320.  
  321.   static outtree(proot)
  322.   PNODE proot;
  323.   /* output the relevant nodes in the quad tree
  324.    *
  325.    * proot - pointer to the root node
  326.    */
  327.   {
  328.     PNODE outnode(), pcur, plast;
  329.  
  330.     /* Set up the linked list with root node */
  331.     pcur = proot;
  332.     plast = proot;
  333.     proot->next = NULL;
  334.  
  335.     /* Output each node on the linked list in order
  336.        until there are no more nodes on the list
  337.      */
  338.     while (pcur != NULL) {
  339.             plast = outnode(pcur, plast);
  340.             pcur = pcur->next;
  341.     }
  342.   }
  343.  
  344.   static PNODE outnode(pnode, plast)
  345.   PNODE pnode, plast;
  346.   /* output the locational code and color index for a
  347.      node and put its children on the list
  348.  
  349.      input:
  350.         pnode  - pointer to node to output
  351.         plast  - pointer to last node on the linked list
  352.  
  353.      output:
  354.         returns pointer to new last node on linked list
  355.    */
  356.   {
  357.     int i;
  358.     PNODE pchild;
  359.  
  360.     /* If node is not a WASH, output it */
  361.     if (pnode->ntype != WASH) {
  362.             putlcc(pnode->locode, pnode->color);
  363.     }
  364.  
  365.     /* Put the node's children on list */
  366.     if (pnode->ntype != LEAF) {
  367.             for (i = 0; i < 4; i++) {
  368.                     pchild = pnode->child[i];
  369.                     if (pchild != NULL) {
  370.                             plast->next = pchild;
  371.                             plast = pchild;
  372.                     }
  373.             }
  374.     }
  375.  
  376.     /* Return new last pointer */
  377.     return(plast);
  378.   }
  379.  
  380.  
  381.  
  382.  
  383.  
  384.   /* Listing two */
  385.   /* Subroutines for displaying an image from a quadtree
  386.      input as locational codes
  387.  
  388.      Written by: Ronald G. White
  389.  
  390.      External routines:
  391.         qdisp - only entry point
  392.  
  393.    */
  394.  
  395.   #include <stdio.h>
  396.  
  397.   extern getnxn();        /* read in next node's data */
  398.   extern filrec();        /* fill rectangular region */
  399.  
  400.   static int orgsize;     /* original image size */
  401.  
  402.   qdisp(size)
  403.   int size;
  404.   /* main entry point for the display of a quadtree
  405.    *
  406.    * input:
  407.    *    size - size of the original image
  408.    */
  409.   {
  410.        int lcode, color;
  411.        int corner[2];
  412.        int side;
  413.  
  414.        /* Make the image size global */
  415.        orgsize = size;
  416.  
  417.        /* Read and display each node */
  418.        while (getnxn(&lcode, &color) != EOF) {
  419.  
  420.          /* Convert loc code to corners, side of square */
  421.          square(lcode, corner, &side);
  422.  
  423.          /* Fill in the square */
  424.          filrec(corner[0], corner[1], side, side, color);
  425.        }
  426.   }
  427.  
  428.   square(lcode, corner, pside)
  429.   int lcode;
  430.   int corner[2];
  431.   int *pside;
  432.   /* convert quadtree locational code to corner and side
  433.      of the square represented by the corresponding node.
  434.  
  435.      input:
  436.         lcode - locational code for this node
  437.  
  438.      output:
  439.         corner - upper left corner of quadrant
  440.         pside  - the size of the quadrant in pixels
  441.    */
  442.   {
  443.        int dir;
  444.        int shift;
  445.  
  446.        corner[0] = corner[1] = 0;
  447.        *pside = orgsize;
  448.  
  449.        /* Find the begining of the code */
  450.        for (shift = 30;
  451.          ((lcode >> shift) & 0xff) == 0; shift -= 2);
  452.  
  453.        /* Convert node locational code to corner row &
  454.           column by looping through direction codes in
  455.           locational code for each level from top down.
  456.         */
  457.        for (shift -= 2; shift >= 0; shift -= 2) {
  458.  
  459.             /* The side of the square is reduced by a
  460.                factor of two each level down.
  461.              */
  462.             *pside >>= 1;
  463.  
  464.             /* extract the direction code */
  465.             dir = (lcode >> shift) & 0x3;
  466.  
  467.             /* increment the col value if quadrant is
  468.                in left half, i.e. NE or SE child
  469.              */
  470.             if (dir == 1 || dir == 3) {
  471.                     corner[0] += *pside;
  472.             }
  473.  
  474.             /* increment the row value if quadrant is
  475.                in bottom half, i.e. SW or SE child
  476.              */
  477.             if (dir == 2 || dir == 3) {
  478.                     corner[1] += *pside;
  479.             }
  480.        }
  481.   }
  482.  
  483.